1. Field of the Invention
This invention is related to the field of digital logic and, more particularly, to circular buffers used in digital logic.
2. Description of the Related Art
Integrated circuits of various types use buffers to store data in an ordered fashion. The order of the data is typically the order in which the data is stored into the buffer over time. Data may be removed from within the buffer (as opposed to only the oldest data, which is at the “bottom” of the buffer), but generally older data (data which was stored in the buffer earlier in time than other data within the buffer) is favored for selection over newer data (data which is stored in the buffer later in time than other data within the buffer).
Buffers may have many different uses in integrated circuits (such as processors). For example, a processor may implement a reorder buffer, a scheduler, a retire queue, a load/store buffer, etc. Each of the above may implement buffers to store various data (e.g. instruction execution results, instructions, addresses of loads/stores, etc.). Generally, a buffer includes multiple entries of equal size. Each of the entries is configured to store a datum.
Buffers may physically be implemented in a number of ways. Two often-used implementations are the shifting buffer and the circular buffer. In the shifting buffer, one entry within the buffer is permanently assigned to be the “bottom” entry in the buffer. A datum being stored into the buffer is stored into the entry which is nearest the bottom entry and which is currently empty. As data is removed from the bottom entries in the buffer, data stored in other entries within the buffer is shifted down such that the bottom entry is filled with the oldest remaining datum and other entries nearest the bottom are filled with the remaining data.
On the other hand, the circular buffer does not shift data from entry to entry. A datum stored into a particular entry in the circular buffer remains in the particular entry. A head pointer (or delete pointer, as used herein) is used to indicate the “bottom” entry, and a tail pointer (or insert pointer, as used herein) is used to indicate the entry into which new data is to be stored. Deleting data from the buffer is accomplished by modifying the head (delete) pointer, and adding data to the buffer is accomplished by storing the data into the entry indicated by the tail pointer and modifying the tail (insert) pointer.
In many ways, the circular buffer may be superior to or equal to the shifting buffer (in terms of complexity, area consumption, speed, power consumption, etc.). However, one way in which the circular buffer may not be superior to the shifting buffer is in finding the first entry having a particular attribute (referred to herein as the “find first” function). That is, locating the first entry, beginning at the head (delete) pointer and moving toward the tail (insert) pointer, that has the particular attribute. In the shifting buffer, the head is fixed and thus the logic for the find first function is straightforward. On the other hand, in the circular buffer, the buffer is effectively scanned beginning at an arbitrary point (the entry indicated by the head (delete) pointer) and ending at an arbitrary point (the entry indicated by the tail (insert) pointer).